import com.sun.org.apache.regexp.internal.RE;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;
import java.util.Stack;

/**
 * Created whit IntelliJ IDEA.
 * Description：
 * User：ZHONGCHEN
 * Date:2022-02-28
 * Time:0:47
 */
public class TestDemo {
    /**
     *1601. 最多可达成的换楼请求数目
     * 我们有 n 栋楼，编号从 0 到 n - 1 。每栋楼有若干员工。由于现在是换楼的季节，部分员工想要换一栋楼居住。
     * 给你一个数组 requests ，其中 requests[i] = [fromi, toi] ，表示一个员工请求从编号为 fromi 的楼搬到编号为 toi 的楼。
     * 一开始 所有楼都是满的，所以从请求列表中选出的若干个请求是可行的需要满足 每栋楼员工净变化为 0 。意思是每栋楼 离开 的员工数目 等于 该楼 搬入 的员工数数目。比方说 n = 3 且两个员工要离开楼 0 ，一个员工要离开楼 1 ，一个员工要离开楼 2 ，如果该请求列表可行，应该要有两个员工搬入楼 0 ，一个员工搬入楼 1 ，一个员工搬入楼 2 。
     * 请你从原请求列表中选出若干个请求，使得它们是一个可行的请求列表，并返回所有可行列表中最大请求数目。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/maximum-number-of-achievable-transfer-requests
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 */
    public static void main(String[] args) {
        int n = 4;
        int[][] requests ={{0,3},{3,1},{1,2},{2,0}};
        //int[][] requests = {{0, 0}, {1, 1}, {0, 0}, {2, 0}, {2, 2}, {1, 1}, {2, 1}, {0, 1}, {0, 1}};
        System.out.println(maximumRequests(n, requests));
    }
    //二进制枚举法
    public static int maximumRequests(int n, int[][] requests) {
        //获取提出更换宿舍的员工个数
        int m = requests.length;
        // max 代表的是员工的状态 -----> 员工请求的请求可以被接受 / 不接受 每个员工有两种状态 那么就有 2^m 次种状态结果
        int maxStatus = 1 << m;
        //记录答案
        int ret = 0;
        //记录是否成功接受请求的数组
        int[] netChangeArr = new int[n];

        //枚举所有状态,二进制中1的个数为当前状态的请求个数
        for (int i = 0; i < maxStatus; i++) {
            int[] tmp = new int[n];
            int state = i;
            //用于记录当前的员工请求下标
            int idx = 0;
            //用于记录当前状态下的接受的请求个数
            int cnt = 0;
            //用于获取当前状态中二进制数字中1的个数
            while (state > 0) {
                //判断最后一位是否为1
                int isAccept = state & 1;
                //如果为1则说明了当前状态被接受了,需要记录住房情况
                if (isAccept == 1) {
                    //获取需要从那里搬到那里的位置信息
                    int from = requests[idx][0];
                    int to = requests[idx][1];
                    //记录住房净变化
                    tmp[from]--;
                    tmp[to]++;
                    cnt++;
                }
                //获取前一个员工的状态请求情况
                state >>= 1;
                idx++;
            }
            //根据上面完成得到的住房记录变化 需要满足每栋楼员工的净变化为0
            if (Arrays.equals(tmp,netChangeArr)){
                ret = Math.max(ret,cnt);
            }
        }
        return ret;
    }

    //判断一个数通过加1或减1能成为斐波那契数的步数
    public static void main2(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        int i = 0;
        int j = 1;
        //当j大于输入的数字时,那么就形成 i<=num<=j的情况;此时算num和i的差值以及num和j的差值即可
        while (j <= num) {
            int tmp = j;
            j = i + j;
            i = j;
            i = tmp;
        }
        System.out.println(Math.min(num - i, j - num));
    }

    //合法括号序列判断
    public static void main3(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();
        int n = scanner.nextInt();
        System.out.println(chkParenthesis(s, n));
    }

    public static boolean chkParenthesis(String A, int n) {
        char[] c = A.toCharArray();
        Stack<Character> stack = new Stack<>();
        for (char c1 : c) {
            if (c1 != '(' && c1 != ')') {
                return false;
            }
            if (c1 == '(') {
                stack.push('(');
            } else {
                if (!stack.empty()) {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        if (stack.empty()) {
            return true;
        }
        return false;
    }
}
